#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#include "SHList.h"

//创建新节点
Node* NewSHListNode(DataType data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    if(NULL == node)
    {
        assert(0);
        return NULL;
    }

    node->next = NULL;
    node->data = data;

    return node;
}

//初始化
void SHListInit(Node** head)
{
    assert(head);
    *head = NewSHListNode(0); //给出头节点（里面的值随便给），头节点的值域不存储任何有效数据
}

//尾插
void SHListPushBack(Node* head, DataType data)
{
    //head就是链表的头指针，*head就是整个链表
    assert(head); //检测带头节点链表的合法性

    Node* cur = head; //head即链表的头节点

    while(cur->next) //找到最后一个节点
    {
        cur = cur->next; //cur->next == 0，cur就是最后一个节点
    }

    cur->next = NewSHListNode(data); //将cur的下一个节点指向新的节点。NewSHListNode返回是Node*,是一个节点
}

//尾删
void SHListPopBack(Node* head)
{
    assert(head); //检测头指针是否存在

    Node* cur = NULL;
    Node* pre = NULL; //初始化两个指针变量

    if(NULL == head->next) //第一种情况：空链表，只有头节点
        return;

    cur = head->next;
    pre = head;
    //第二种情况：非空链表：包括1个节点和多个节点
    while(cur->next) //找到最后一个节点，保留最后一个节点的前一个结点
    {
        pre = cur;
        cur = cur->next;
    }

    free(cur);
    pre->next = NULL;
}

//头插
void SHListPushFront(Node* head, DataType data)
{
    assert(head);

    Node* newNode = NewSHListNode(data);
    newNode->next = head->next;
    head->next = newNode;
}

//头删
void SHListPopFront(Node* head)
{
    assert(head);

    if(NULL == head->next) //只有头节点，则返回
        return;
    //else if(NULL == head->next->next) //只有一个有效元素节点
    //{
    //    Node* cur = head->next;
    //    free(head->next);
    //    cur = NULL;
    //}
    Node* cur = head->next;
    head->next = cur->next;
    free(cur);
}

//任意位置的插入，只能插入到pos位置的下一个位置
void SHListInsert(Node* pos, DataType data)
{
    if(NULL == pos)
        return;

    Node* newNode = NewSHListNode(data);
    newNode->next = pos->next;
    pos->next = newNode;
}

//任意位置的删除,只能删除pos位置的下一个元素
void SHListErase(Node* pos)
{
    if(NULL == pos || NULL == pos->next)
        return;

    Node* cur = pos->next;
    pos->next = cur->next;
    free(cur); //先链接，再free。如果先free,就不能链接后面的节点
}

//获得有效元素的大小，遍历
int SHListSize(Node* head)
{
    int count = 0;
    Node* cur = head->next;
    while(cur)
    {
        ++count;
        cur = cur->next;
    }
    return count;
}

//查找，注意返回的是节点
Node* SHListFind(Node* head, DataType data)
{
    assert(head);

    Node* cur = head->next;
    while(cur)
    {
        if(data == cur->data)
            return cur; //返回是节点，不是data

        cur = cur->next;
    }

    return NULL;
}

//销毁，不管有没有头节点，销毁必须传二级指针
void SHListDestroy(Node** head)
{
    //Node* cur1 = (*head)->next;
    //Node* cur2 = NULL;
    //while(NULL != cur1) //先把头节点以后的所有节点销毁
    //{
    //    cur2 = cur1;
    //    free(cur1);
    //    cur1 = cur2->next;
    //}
    //free(*head); //再销毁头节点
    Node* cur = NULL;
    while(*head) 
    {
        cur = *head;
        free(cur);
        *head = cur->next;
    }
}

//测试
void SHListPrint(Node* head)
{
    Node* cur = head->next;
    while(cur)
    {
        printf("%d--->",cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
